package com.eatme.core.sort;

import com.eatme.core.array.ArrayGenerator;

import java.util.Arrays;
import java.util.Random;

public class QuickSortV3 {
    private QuickSortV3() {

    }

    public static <E extends  Comparable<E>> void sort(E[] arr) {
        Random rnd = new Random();
        sort(arr,0,arr.length-1,rnd);
    }

    private static <E extends  Comparable<E>> void sort(E[] arr, int l, int r, Random rnd) {
        if (l>=r) return;
        int p = partition(arr,l,r,rnd);
        sort(arr,l,p-1, rnd);
        sort(arr,p+1,r, rnd);
    }

    private static <E extends  Comparable<E>> int partition(E[] arr,int l,int r,Random rnd) {
        // arr[l+1...j] < v; arr[j+1...i] >= v
        int p = l+rnd.nextInt(r-l+1);
        swap(arr,l,p);
        int j = l;
        for (int i = l+1; i <= r; i++)
            if (arr[i].compareTo(arr[l])<0) {
                j++;
                swap(arr, i, j);
            }
        swap(arr,l,j);
        return j;
    }

    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr[i];
        arr[i] =arr[j];
        arr[j] =t;
    }

    public static void main(String[] args) {
        int n = 1000000;
        System.out.println("RandomArray");
        Integer[] arr =ArrayGenerator.generateRandomArray(n,n);
        Integer[] arr2 = Arrays.copyOf(arr,arr.length);
        Integer[] arr3 = Arrays.copyOf(arr,arr.length);
        Integer[] arr4 = Arrays.copyOf(arr,arr.length);
        Integer[] arr4_1 = Arrays.copyOf(arr,arr.length);
        Integer[] arr4_2 = Arrays.copyOf(arr,arr.length);
        Integer[] arr4_3 = Arrays.copyOf(arr,arr.length);
        Integer[] arr4_4 = Arrays.copyOf(arr,arr.length);
        SortingHelper.sortTest("QuickSortV3",arr4_4);
//        SortingHelper.sortTest("MergeSort",arr);
//        SortingHelper.sortTest("MergeSortV2",arr4);
//        SortingHelper.sortTest("MergeSortV3",arr4_1);
//        SortingHelper.sortTest("MergeSortV4",arr4_2);
//        SortingHelper.sortTest("MergeSortBU",arr4_3);

        System.out.println("OrderedArray");
        Integer[] arr5 =ArrayGenerator.generateOrderedArray(n);
        Integer[] arr6 = Arrays.copyOf(arr5,arr.length);
        SortingHelper.sortTest("QuickSortV3",arr6);

    }
}
